package com.fh.binarysearch;
// T4
class T4FindMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 保证 nums1 是较短的数组，以减少二分查找的范围
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int totalLeft = (m + n + 1) / 2; // 左半部分的总长度

        // 在较短的数组 nums1 的区间 [0, m] 里查找恰当的分割线
        int left = 0;
        int right = m;

        while (left < right) {
            // i 表示 nums1 中左半部分的元素个数
            // 使用 (m + n + 1) / 2（整数除法）可以保证：
            //当 k为奇数时，左半部分比右半部分多一个元素（中位数恰好是左半部分的最大值）。
            //当 k为偶数时，左半部分和右半部分元素个数相等（中位数由左半部分最大值和右半部分最小值计算得出）。
            //这样无论总长度是奇是偶，左半部分始终包含中位数或中位数的左侧组成部分，无需在后续计算中额外判断奇偶性
            int i = left + (right - left + 1) / 2;
            // j 表示 nums2 中左半部分的元素个数
            int j = totalLeft - i;

            // 检查 nums1 分割线左侧的最大值是否大于 nums2 分割线右侧的最小值
            if (nums1[i - 1] > nums2[j]) {
                // 下一轮搜索的区间 [left, i - 1]
                right = i - 1;
            } else {
                // 下一轮搜索的区间 [i, right]
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;

        // 处理数组为空的情况，确定分割线左右两侧的值
        int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

        if (((m + n) % 2) == 1) {
            // 如果总长度为奇数，中位数为分割线左侧的最大值
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            // 如果总长度为偶数，中位数为（左边最大值 + 右边最小值）/ 2.0
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
        }
    }
}